/*
    202006021516
    例3-3：写一个不带头节点的链栈
    实现初始化、判断栈空、进栈、出栈等算法
*/

#include <iostream>
#include <stdio.h>
//#include <malloc.h>   //OSX的gcc貌似不需要malloc.h头文件
using namespace std;

#define MAXSIZE 10

//链栈的结点定义
typedef struct LNode
{
    int data;
    struct LNode *next;
} LNode;

void initStack(LNode *&);   //初始化栈
int isEmpty(LNode *);       //判空
void pushl(LNode *&, int);  //入栈
int popl(LNode *&, int &); //出栈

int main(void)
{
    LNode *p;
    initStack(p);
    for (int i = 0; i < MAXSIZE; i++)
    {
        pushl(p,i+1);
    }
    for(int i = 0; i < 12; i++)
    {
        int x;
        if(popl(p,x))
            cout << x << endl;
        else 
            cout << "出栈失败" << endl;
    }
    
    
    cout << "finish!" << endl;
    return 0;
}

/*
    不带头结点的单链表的lst为空的条件是lst == NULL,入栈和出栈都是在
    表头进行的，如下列程序所示
*/
void initStack(LNode *&lst)
{
    lst = NULL;
}

//判断栈空
int isEmpty(LNode *lst)
{
    if (lst == NULL)
        return 1;
    else
        return 0;
}

//入栈
void pushl(LNode *&lst, int x)
{
    LNode *p;
    p = (LNode *)malloc(sizeof(LNode));
    p->next = NULL;
    p->data = x;

    p->next = lst;  //新结点指向头结点
    lst = p;    //新结点成为新的头结点
}

int popl(LNode *&lst, int &x)
{
    LNode *p;
    if(lst == NULL)
        return 0;   //表空直接返回0
    p = lst;

    //就是单链表的删除操作
    x = p->data;
    lst = p->next;
    free(p);
    return 1;
}